package linkedlist;

import java.math.BigDecimal;
import java.util.Stack;

/**
 * @author tong
 * @date 2021/12/22 14:32
 * 单链表crud
 */
public class SingleLinkedList {

    private Node<Person> head = new Node<>(new Person());

    public void add(Node<Person> node) {
        Node<Person> temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = node;
    }

    public void list() {
        if (head.next == null) {
            System.out.println("empty");
            return;
        }
        Node<Person> temp = head;
        while (true) {
            if (temp == null) {
                break;
            }
            System.out.println(temp.data);
            temp = temp.next;
        }
    }

    public void insert(Node<Person> node) {
        Node<Person> temp = head;
        while (true) {
            if (temp.next == null || temp.next.data.getNo() > node.data.getNo()) {
                break;
                //和下一个节点比较
            } else if (temp.next.data.getNo() == node.data.getNo()) {
                System.out.println(temp.next.data.getNo() + "exist!");
                return;
            }
            temp = temp.next;
        }
        node.next = temp.next;
        temp.next = node;
    }

    public void update(Node<Person> node) {
        if (head.next == null) {
            System.out.println("empty");
            return;
        }
        Node<Person> temp = head;
        while (true) {
            if (temp == null) {
                System.out.println("not found");
                return;
            }
            if (temp.data.getNo() == node.data.getNo()) {
                break;
            }
            temp = temp.next;
        }
        temp.data.setName(node.data.getName());
    }

    public void delete(int no) {
        Node<Person> temp = head;
        while (true) {
            if (temp.next == null) {
                System.out.println("not exists");
                return;
            }
            if (temp.next.data.getNo() == no) {
                break;
            }
            temp = temp.next;
        }
        temp.next = temp.next.next;
    }

    public static void main(String[] args) {
        // 测试
        SingleLinkedList list1 = new SingleLinkedList();
        Node<Person> node1 = new Node<>(new Person(1, "a"));
        Node<Person> node3 = new Node<>(new Person(3, "c"));
        Node<Person> node5 = new Node<>(new Person(5, "e"));
        list1.add(node1);
        list1.add(node3);
        list1.add(node5);
        SingleLinkedList list2 = new SingleLinkedList();
        Node<Person> node2 = new Node<>(new Person(2, "b"));
        Node<Person> node4 = new Node<>(new Person(4, "d"));
        list2.add(node2);
        list2.add(node4);
        Node<Person> node = sumLinkedList(list1.head, list2.head);
        System.out.println(node);
    }


    /**
     * 合并两个有序单链表
     *
     * @param head1
     * @param head2
     * @return
     */
    public static Node<Person> sumLinkedList(Node<Person> head1, Node<Person> head2) {

        Node<Person> head = new Node<>(new Person(0, null), null);
        Node<Person> temp = head;
        while (head1 != null && head2 != null) {
            if (head1.data.getNo() > head2.data.getNo()) {
                temp.next = head2;
                head2 = head2.next;
            } else {
                temp.next = head1;
                head1 = head1.next;
            }
            temp = temp.next;
        }
        if (head1 != null) {
            temp.next = head1;
        }
        if (head2 != null) {
            temp.next = head2;
        }
        return head.next.next;
    }

    /**
     * 逆序打印-栈实现
     *
     * @param node
     */
    public static void reversePrint(Node<Person> node) {
        Stack<Node<Person>> stack = new Stack<>();
        Node<Person> cur = node.next;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        while (!stack.isEmpty()) {
            System.out.println(stack.pop().data);
        }
    }

    /**
     * 有效节点个数-不含头节点的链表长度
     *
     * @param node
     * @return
     */
    public static int getLength(Node<Person> node) {
        int length = 0;
        while (node.next != null) {
            length++;
            node = node.next;
        }
        return length;
    }

    /**
     * 查找单链表中的倒数第k个结点
     *
     * @param node
     * @param index
     * @return
     */
    public static Node<Person> findLastIndexNode(Node<Person> node, int index) {
        Node<Person> fast = node.next;
        Node<Person> slow = node.next;
        while (index > 0) {
            index--;
            fast = fast.next;
            if (fast == null) {
                return null;
            }
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    /**
     * 翻转单链表
     *
     * @param node
     */
    public static void reverseList(Node<Person> node) {
        // 无需翻转
        if (node.next == null || node.next.next == null) {
            return;
        }
        // 头插法
        Node<Person> reverseHead = new Node<>(new Person(0, null), null);
        // 当前操作节点
        Node<Person> cur = node.next;
        // 存储当前节点的下一节点
        Node<Person> next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = reverseHead.next;
            reverseHead.next = cur;
            cur = next;
        }
        node.next = reverseHead.next;
    }
}
